// 501. 二叉搜索树中的众数
// https://leetcode.cn/problems/find-mode-in-binary-search-tree/
// 简单,给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
// 如果树中有不止一个众数，可以按 任意顺序 返回。
// 假定 BST 满足如下定义：
// 结点左子树中所含节点的值 小于等于 当前节点的值
// 结点右子树中所含节点的值 大于等于 当前节点的值
// 左子树和右子树都是二叉搜索树
// 示例 1：
// 输入：root = [1,null,2,2]
// 输出：[2]
// 示例 2：
// 输入：root = [0]
// 输出：[0]
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int curVal = 0;
    int count = 0;
    int maxCnt = 0;
    vector<int> ans;
    void record(int x) {
        if (x == curVal) {
            count++;
        } else {
            count = 1;
            curVal = x;
        }
        if (maxCnt == count) {
            ans.push_back(curVal);
        } else if (maxCnt < count) {
            ans.clear();
            ans.push_back(curVal);
            maxCnt = count;
        }
    }
    void dfs(TreeNode* root) {
        if (!root) {
            return ;
        }
        dfs(root->left);
        record(root->val);
        dfs(root->right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

int main() {
    return 0;
}
